package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //子集
        class Solution {
            List<List<Integer>> result;
            List<Integer> path;

            public List<List<Integer>> subsets(int[] nums) {
                result = new ArrayList<>();
                path = new ArrayList<>();
                dfs(nums, 0);
                return result;
            }

            private void dfs(int[] nums, int k) {
                // 1) 任何时刻的路径都是一个合法子集
                result.add(new ArrayList<>(path));

                // 2) 从当前位置开始，依次尝试选择一个元素加入
                for (int i = k; i < nums.length; i++) {
                    path.add(nums[i]);           // 选择
                    dfs(nums, i + 1);            // 递归到下一个起点
                    path.remove(path.size() - 1);// 回退
                }
            }
        }

        //找出所有子集的异或总和再求和
        class Solution2 {
            List<List<Integer>> ret;
            List<Integer> path;

            public int subsetXORSum(int[] nums) {
                int result = 0;
                ret = new ArrayList<>();
                path = new ArrayList<>();

                // 可选：排序对异或结果无影响，通常无需
                // Arrays.sort(nums);

                dfs(nums, 0);

                // 遍历每个子集，计算其异或值并累加
                for (List<Integer> cur : ret) {
                    int xor = 0;
                    for (int x : cur) {
                        xor ^= x;
                    }
                    result += xor;
                }
                return result;
            }

            // 回溯生成所有子集：从索引 k 开始做选择
            private void dfs(int[] nums, int k) {
                // 当前路径就是一个合法子集
                ret.add(new ArrayList<>(path));

                // 从 k 开始依次选择一个元素加入
                for (int i = k; i < nums.length; i++) {
                    path.add(nums[i]);         // 选择
                    dfs(nums, i + 1);          // 递归到下一个起点
                    path.remove(path.size() - 1); // 回退
                }
            }
        }
    }
}